home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / yacc.arc / Y3.C < prev    next >
Text File  |  1985-09-04  |  10KB  |  409 lines
  1. #include "c:dextern"
  2.  
  3.     /* important local variables */
  4. int lastred;  /* the number of the last reduction of a state */
  5. int defact[NSTATES];  /* the default actions of states */
  6.  
  7. output(){ /* print the output for the states */
  8.  
  9.     int i, k, c;
  10.     register struct wset *u, *v;
  11.  
  12.     fprintf( ftable, "short yyexca[] ={\n" );
  13.  
  14.     SLOOP(i) { /* output the stuff for state i */
  15.         nolook = !(tystate[i]==MUSTLOOKAHEAD);
  16.         closure(i);
  17.         /* output actions */
  18.         nolook = 1;
  19.         aryfil( temp1, ntokens+nnonter+1, 0 );
  20.         WSLOOP(wsets,u){
  21.             c = *( u->pitem );
  22.             if( c>1 && c<NTBASE && temp1[c]==0 ) {
  23.                 WSLOOP(u,v){
  24.                     if( c == *(v->pitem) ) putitem( v->pitem+1, (struct looksets *)0 );
  25.                     }
  26.                 temp1[c] = state(c);
  27.                 }
  28.             else if( c > NTBASE && temp1[ (c -= NTBASE) + ntokens ] == 0 ){
  29.                 temp1[ c+ntokens ] = amem[indgo[i]+c];
  30.                 }
  31.             }
  32.  
  33.         if( i == 1 ) temp1[1] = ACCEPTCODE;
  34.  
  35.         /* now, we have the shifts; look at the reductions */
  36.  
  37.         lastred = 0;
  38.         WSLOOP(wsets,u){
  39.             c = *( u->pitem );
  40.             if( c<=0 ){ /* reduction */
  41.                 lastred = -c;
  42.                 TLOOP(k){
  43.                     if( BIT(u->ws.lset,k) ){
  44.                           if( temp1[k] == 0 ) temp1[k] = c;
  45.                           else if( temp1[k]<0 ){ /* reduce/reduce conflict */
  46.                             if( foutput!=NULL )
  47.                               fprintf( foutput,
  48.                                 "\n%d: reduce/reduce conflict (red'ns %d and %d ) on %s",
  49.                                 i, -temp1[k], lastred, symnam(k) );
  50.                             if( -temp1[k] > lastred ) temp1[k] = -lastred;
  51.                             ++zzrrconf;
  52.                             }
  53.                           else { /* potential shift/reduce conflict */
  54.                             precftn( lastred, k, i );
  55.                             }
  56.                         }
  57.                     }
  58.                 }
  59.             }
  60.         wract(i);
  61.         }
  62.  
  63.     fprintf( ftable, "\t};\n" );
  64.  
  65.     wdef( "YYNPROD", nprod );
  66.  
  67.     }
  68.  
  69. int pkdebug = 0;
  70. apack(p, n ) int *p;{ /* pack state i from temp1 into amem */
  71.     int off;
  72.     register *pp, *qq, *rr;
  73.     int *q, *r;
  74.  
  75.     /* we don't need to worry about checking because we
  76.        we will only look entries known to be there... */
  77.  
  78.     /* eliminate leading and trailing 0's */
  79.  
  80.     q = p+n;
  81.     for( pp=p,off=0 ; *pp==0 && pp<=q; ++pp,--off ) /* VOID */ ;
  82.     if( pp > q ) return(0);  /* no actions */
  83.     p = pp;
  84.  
  85.     /* now, find a place for the elements from p to q, inclusive */
  86.  
  87.     r = &amem[ACTSIZE-1];
  88.     for( rr=amem; rr<=r; ++rr,++off ){  /* try rr */
  89.         for( qq=rr,pp=p ; pp<=q ; ++pp,++qq){
  90.             if( *pp != 0 ){
  91.                 if( *pp != *qq && *qq != 0 ) goto nextk;
  92.                 }
  93.             }
  94.  
  95.         /* we have found an acceptable k */
  96.  
  97.         if( pkdebug && foutput!=NULL ) fprintf( foutput, "off = %d, k = %d\n", off, rr-amem );
  98.  
  99.         for( qq=rr,pp=p; pp<=q; ++pp,++qq ){
  100.             if( *pp ){
  101.                 if( qq > r ) error( "action table overflow" );
  102.                 if( qq>memp ) memp = qq;
  103.                 *qq = *pp;
  104.                 }
  105.             }
  106.         if( pkdebug && foutput!=NULL ){
  107.             for( pp=amem; pp<= memp; pp+=10 ){
  108.                 fprintf( foutput, "\t");
  109.                 for( qq=pp; qq<=pp+9; ++qq ) fprintf( foutput, "%d ", *qq );
  110.                 fprintf( foutput, "\n");
  111.                 }
  112.             }
  113.         return( off );
  114.  
  115.         nextk: ;
  116.         }
  117.     error("no space in action table" );
  118.     /* NOTREACHED */
  119.     }
  120.  
  121. go2out(){ /* output the gotos for the nontermninals */
  122.     int i, j, k, best, count, cbest, times;
  123.  
  124.     fprintf( ftemp, "$\n" );  /* mark begining of gotos */
  125.  
  126.     for( i=1; i<=nnonter; ++i ) {
  127.         go2gen(i);
  128.  
  129.         /* find the best one to make default */
  130.  
  131.         best = -1;
  132.         times = 0;
  133.  
  134.         for( j=0; j<=nstate; ++j ){ /* is j the most frequent */
  135.             if( tystate[j] == 0 ) continue;
  136.             if( tystate[j] == best ) continue;
  137.  
  138.             /* is tystate[j] the most frequent */
  139.  
  140.             count = 0;
  141.             cbest = tystate[j];
  142.  
  143.             for( k=j; k<=nstate; ++k ) if( tystate[k]==cbest ) ++count;
  144.  
  145.             if( count > times ){
  146.                 best = cbest;
  147.                 times = count;
  148.                 }
  149.             }
  150.  
  151.         /* best is now the default entry */
  152.  
  153.         zzgobest += (times-1);
  154.         for( j=0; j<=nstate; ++j ){
  155.             if( tystate[j] != 0 && tystate[j]!=best ){
  156.                 fprintf( ftemp, "%d,%d,", j, tystate[j] );
  157.                 zzgoent += 1;
  158.                 }
  159.             }
  160.  
  161.         /* now, the default */
  162.  
  163.         zzgoent += 1;
  164.         fprintf( ftemp, "%d\n", best );
  165.  
  166.         }
  167.  
  168.  
  169.  
  170.     }
  171.  
  172. int g2debug = 0;
  173. go2gen(c){ /* output the gotos for nonterminal c */
  174.  
  175.     int i, work, cc;
  176.     struct item *p, *q;
  177.  
  178.  
  179.     /* first, find nonterminals with gotos on c */
  180.  
  181.     aryfil( temp1, nnonter+1, 0 );
  182.     temp1[c] = 1;
  183.  
  184.     work = 1;
  185.     while( work ){
  186.         work = 0;
  187.         PLOOP(0,i){
  188.             if( (cc=prdptr[i][1]-NTBASE) >= 0 ){ /* cc is a nonterminal */
  189.                 if( temp1[cc] != 0 ){ /* cc has a goto on c */
  190.                     cc = *prdptr[i]-NTBASE; /* thus, the left side of production i does too */
  191.                     if( temp1[cc] == 0 ){
  192.                           work = 1;
  193.                           temp1[cc] = 1;
  194.                           }
  195.                     }
  196.                 }
  197.             }
  198.         }
  199.  
  200.     /* now, we have temp1[c] = 1 if a goto on c in closure of cc */
  201.  
  202.     if( g2debug && foutput!=NULL ){
  203.         fprintf( foutput, "%s: gotos on ", nontrst[c].name );
  204.         NTLOOP(i) if( temp1[i] ) fprintf( foutput, "%s ", nontrst[i].name);
  205.         fprintf( foutput, "\n");
  206.         }
  207.  
  208.     /* now, go through and put gotos into tystate */
  209.  
  210.     aryfil( tystate, nstate, 0 );
  211.     SLOOP(i){
  212.         ITMLOOP(i,p,q){
  213.             if( (cc= *p->pitem) >= NTBASE ){
  214.                 if( temp1[cc -= NTBASE] ){ /* goto on c is possible */
  215.                     tystate[i] = amem[indgo[i]+c];
  216.                     break;
  217.                     }
  218.                 }
  219.             }
  220.         }
  221.     }
  222.  
  223. precftn(r,t,s){ /* decide a shift/reduce conflict by precedence.
  224.     /* r is a rule number, t a token number */
  225.     /* the conflict is in state s */
  226.     /* temp1[t] is changed to reflect the action */
  227.  
  228.     int lp,lt, action;
  229.  
  230.     lp = levprd[r];
  231.     lt = toklev[t];
  232.     if( PLEVEL(lt) == 0 || PLEVEL(lp) == 0 ) {
  233.         /* conflict */
  234.         if( foutput != NULL ) fprintf( foutput, "\n%d: shift/reduce conflict (shift %d, red'n %d) on %s",
  235.                         s, temp1[t], r, symnam(t) );
  236.         ++zzsrconf;
  237.         return;
  238.         }
  239.     if( PLEVEL(lt) == PLEVEL(lp) ) action = ASSOC(lt);
  240.     else if( PLEVEL(lt) > PLEVEL(lp) ) action = RASC;  /* shift */
  241.     else action = LASC;  /* reduce */
  242.  
  243.     switch( action ){
  244.  
  245.     case BASC:  /* error action */
  246.         temp1[t] = ERRCODE;
  247.         return;
  248.  
  249.     case LASC:  /* reduce */
  250.         temp1[t] = -r;
  251.         return;
  252.  
  253.         }
  254.     }
  255.  
  256. wract(i){ /* output state i */
  257.     /* temp1 has the actions, lastred the default */
  258.     int p, p0, p1;
  259.     int ntimes, tred, count, j;
  260.     int flag;
  261.  
  262.     /* find the best choice for lastred */
  263.  
  264.     lastred = 0;
  265.     ntimes = 0;
  266.     TLOOP(j){
  267.         if( temp1[j] >= 0 ) continue;
  268.         if( temp1[j]+lastred == 0 ) continue;
  269.         /* count the number of appearances of temp1[j] */
  270.         count = 0;
  271.         tred = -temp1[j];
  272.         levprd[tred] |= REDFLAG;
  273.         TLOOP(p){
  274.             if( temp1[p]+tred == 0 ) ++count;
  275.             }
  276.         if( count >ntimes ){
  277.             lastred = tred;
  278.             ntimes = count;
  279.             }
  280.         }
  281.  
  282.     /* for error recovery, arrange that, if there is a shift on the
  283.     /* error recovery token, `error', that the default be the error action *
  284. /
  285.     if( temp1[1] > 0 ) lastred = 0;
  286.  
  287.     /* clear out entries in temp1 which equal lastred */
  288.     TLOOP(p) if( temp1[p]+lastred == 0 )temp1[p]=0;
  289.  
  290.     wrstate(i);
  291.     defact[i] = lastred;
  292.  
  293.     flag = 0;
  294.     TLOOP(p0){
  295.         if( (p1=temp1[p0])!=0 ) {
  296.             if( p1 < 0 ){
  297.                 p1 = -p1;
  298.                 goto exc;
  299.                 }
  300.             else if( p1 == ACCEPTCODE ) {
  301.                 p1 = -1;
  302.                 goto exc;
  303.                 }
  304.             else if( p1 == ERRCODE ) {
  305.                 p1 = 0;
  306.                 goto exc;
  307.             exc:
  308.                 if( flag++ == 0 ) fprintf( ftable, "-1, %d,\n", i );
  309.                 fprintf( ftable, "\t%d, %d,\n", tokset[p0].value, p1 );
  310.                 ++zzexcp;
  311.                 }
  312.             else {
  313.                 fprintf( ftemp, "%d,%d,", tokset[p0].value, p1 );
  314.                 ++zzacent;
  315.                 }
  316.             }
  317.         }
  318.     if( flag ) {
  319.         defact[i] = -2;
  320.         fprintf( ftable, "\t-2, %d,\n", lastred );
  321.         }
  322.     fprintf( ftemp, "\n" );
  323.     return;
  324.     }
  325.  
  326. wrstate(i){ /* writes state i */
  327.     register j0,j1;
  328.     register struct item *pp, *qq;
  329.     register struct wset *u;
  330.  
  331.     if( foutput == NULL ) return;
  332.     fprintf( foutput, "\nstate %d\n",i);
  333.     ITMLOOP(i,pp,qq) fprintf( foutput, "\t%s\n", writem(pp->pitem));
  334.     if( tystate[i] == MUSTLOOKAHEAD ){
  335.         /* print out empty productions in closure */
  336.         WSLOOP( wsets+(pstate[i+1]-pstate[i]), u ){
  337.             if( *(u->pitem) < 0 ) fprintf( foutput, "\t%s\n", writem(u->pitem) );
  338.             }
  339.         }
  340.  
  341.     /* check for state equal to another */
  342.  
  343.     TLOOP(j0) if( (j1=temp1[j0]) != 0 ){
  344.         fprintf( foutput, "\n\t%s  ", symnam(j0) );
  345.         if( j1>0 ){ /* shift, error, or accept */
  346.             if( j1 == ACCEPTCODE ) fprintf( foutput,  "accept" );
  347.             else if( j1 == ERRCODE ) fprintf( foutput, "error" );
  348.             else fprintf( foutput,  "shift %d", j1 );
  349.             }
  350.         else fprintf( foutput, "reduce %d",-j1 );
  351.         }
  352.  
  353.     /* output the final production */
  354.  
  355.     if( lastred ) fprintf( foutput, "\n\t.  reduce %d\n\n", lastred );
  356.     else fprintf( foutput, "\n\t.  error\n\n" );
  357.  
  358.     /* now, output nonterminal actions */
  359.  
  360.     j1 = ntokens;
  361.     for( j0 = 1; j0 <= nnonter; ++j0 ){
  362.         if( temp1[++j1] ) fprintf( foutput, "\t%s  goto %d\n", symnam( j0+NTBASE), temp1[j1] );
  363.         }
  364.  
  365.     }
  366.  
  367. wdef( s, n ) char *s; { /* output a definition of s to the value n */
  368.     fprintf( ftable, "# define %s %d\n", s, n );
  369.     }
  370.  
  371. warray( s, v, n ) char *s; int *v, n; {
  372.  
  373.     register i;
  374.  
  375.     fprintf( ftable, "short %s[]={\n", s );
  376.     for( i=0; i<n; ){
  377.         if( i%10 == 0 ) fprintf( ftable, "\n" );
  378.         fprintf( ftable, "%4d", v[i] );
  379.         if( ++i == n ) fprintf( ftable, " };\n" );
  380.         else fprintf( ftable, "," );
  381.         }
  382.     }
  383.  
  384. hideprod(){
  385.     /* in order to free up the mem and amem arrays for the optimizer,
  386.     /* and still be able to output yyr1, etc., after the sizes of
  387.     /* the action array is known, we hide the nonterminals
  388.     /* derived by productions in levprd.
  389.     */
  390.  
  391.     register i, j;
  392.  
  393.     j = 0;
  394.     levprd[0] = 0;
  395.     PLOOP(1,i){
  396.         if( !(levprd[i] & REDFLAG) ){
  397.             ++j;
  398.             if( foutput != NULL ){
  399.                 fprintf( foutput, "Rule not reduced:   %s\n", writem( prdptr[i] ) );
  400.                 }
  401.             }
  402.         levprd[i] = *prdptr[i] - NTBASE;
  403.         }
  404.     if( j ) fprintf( stdout, "%d rules never reduced\n", j );
  405.     }
  406.  
  407.  
  408.  
  409.